/*
 * @Author: yuzezhong 
 * @Date: 2019-06-06 10:02:40 
 * @Last Modified by: yuzezhong
 * @Last Modified time: 2019-06-06 11:18:02
 * 算法要求数组中的元素都在0~k之间，所以相当于已知
 * 数组中的最大元素，这是算法的局限性
 */

#include <iostream>
#include <vector>

using namespace std;

void countingsort(vector<int> a, int k)
{
    vector<int> count(k + 1, 0);//作为计数的数组要为k+1,保存1~k的整数
    vector<int> res(a.size(), 0);
    for (int i = 0; i < a.size(); i++)
        count[a.at(i)] += 1;
    for (int i = 1; i <= k; i++)
        count.at(i) += count.at(i - 1);
    for (int i = a.size() - 1; i >= 0; i--)
        res[--count[a.at(i)]] = a.at(i);

    for (int i = 0; i < res.size(); i++)
        cout << "the " << i << "th element is " << res.at(i) << endl;
}

int main(int argc, char const *argv[])
{
    const int k = 100; //设数组最大元素为100
    vector<int> a(50, 0);

    for (int i = 0; i < 50; i++)
    {
        a.at(i) = random() % 100 + 1;
    }

    countingsort(a, k);

    return 0;
}
